home *** CD-ROM | disk | FTP | other *** search
- Newsgroups: comp.lang.java,comp.lang.c,comp.lang.c++
- Path: netcom.com!NewsWatcher!user
- From: hbaker@netcom.com (Henry Baker)
- Subject: Correct mod/rem (was: Problem with % (remainder) operator
- Message-ID: <hbaker-2201961022380001@10.0.2.15>
- Sender: hbaker@netcom12.netcom.com
- Organization: nil organization
- References: <4dc86s$gha@news.xs4all.nl> <4d8hnd$74h@news.xs4all.nl> <443322587wnr@almide.demon.co.uk> <142091149wnr@almide.demon.co.uk> <4dguci$le3@news.ox.ac.uk>
- Date: Mon, 22 Jan 1996 18:22:38 GMT
-
- This problem has been discussed ad nauseum in every single comp.lang
- newsgroup, and it seems to be that every language gets it wrong in the
- first n iterations, so that the implementers of the new languages keep
- copying the wrong code from their previous language.
-
- The usual justification for getting it wrong is that 'that's what the
- hardware does, and we want fast code'. Of course, once the language gets
- established and _portability_ to a wide variety of machines becomes important,
- it becomes necessary to try to retrofit a fully specified function, thus
- breaking many existing programs.
-
- So far as I know, only APL and Common Lisp have attempted to get 'mod' right.
-
- 'Everybody' thinks they know how division works, because they all learned it
- in graded school.
-
- OK, so what did you learn? Given a 'dividend' N and a 'divisor' D, we need
- to compute a 'quotient' Q, and a 'remainder' R. What properties do we want
- from this quotient Q and this remainder R?
-
- The first property is that N = Q*D + R. Otherwise, the whole meaning of
- 'remainder' is lost -- i.e., that part that 'remains' after taking out Q
- copies of D from N.
-
- Fine, so we simply set Q=0, R=N. 'You can't do that," you say. Why? Because
- then division didn't _do_ anything, it didn't make R 'small'.
-
- Why do we need R 'small'? Well, if we're converting binary to decimal, and
- we divide our binary number by 10 and get as a remainder our original binary
- number, we will need an awful lot of decimal 'digits' :-). So, using base
- conversion as a _criterion_, we add the additional constraint that
-
- 0 <= |R| < |D|.
-
- In other words, we want the absolute value of the 'remainder' to be smaller
- than the absolute value of the divisor.
-
- However, this still doesn't pin down the answer. For example, if we divide
- 27 by 10, we can get two different quotients and remainders:
-
- (I) 27 = 2*10 + 7 i.e., Q=2, R=7
-
- (II) 27 = 3*10 + (-3) i.e., Q=3, R=-3
-
- Going back to our decimal conversion problem again, we decide that the
- most appropriate choice is the first, not the second, since we want base
- conversion to 'work' correctly.
-
- We therefore refine our constraints, but find that we still have two choices
- when the divisor is _negative_.
-
- (I) 0 <= R < |D|
-
- (II) 0 <= R*D < D^2
-
- For example, if we divide 27 by -10, we can still get two different quotients
- and remainders:
-
- (I) 27 = (-2)*(-10) + 7 i.e., Q=-2, R=7
-
- (II) 27 = (-3)*(-10) + (-3) i.e., Q=-3, R=-3
-
- Once again, we appeal to the base conversion algorithm for our answer. In
- the case of a negative divisor, we _expect_ negative digits -- indeed, we
- _demand_ them, so that the correct choice is (II), which can be expressed
- by the rule "sign of remainder follows sign of the divisor" (NOT, sign of
- the dividend, like lots of brain-damaged computer hardware).
-
- The nice thing about the "sign of the divisor" choice is that the quotient
- is easily expressed as the 'floor' function: Q = floor[N/D].
-
- ----
-
- There is another division function called 'round' which tries to find the
- 'closest' integer to the rational quotient. As might be expected, the
- remainders produced by 'round' are smaller than those produced by 'floor',
- and are both positive and negative:
-
- 0 <= |R| <= |D|/2
-
- This is well-defined if D is an odd integer, but is ambiguous if D is even.
- There are several competing definitions for what to do if D is even: one of
- them is 'if N/D falls half way between two integers, choose the even one
- as the quotient'. This rule is similar to one that is used by numerical
- analysts as an 'unbiased' rounding rule, and is used by some IEEE float
- implementations.
-
- Base conversion sometimes uses remainders produced by 'round' instead of
- 'floor'. For example, hardware multipliers often convert to a 'balanced'
- notation. If we were doing decimal, then we would use the 'digits'
- -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, instead of 5, 6, 7, 8, 9, 0, 1, 2, 3, 4,
- respectively, because it reduces the number of carries that have to propagate.
-
- (Those who know about implementations of GCD, also know that 'round' produces
- the GCD in the least number of iterations.)
-
- -----
-
- To summarize, the 'correct' mod is one that produces remainders that follow
- the _divisor_, and therefore the 'correct' quotient is the _floor_ function.
- If your language allows more than one, then the next one should be the
- 'round' function (& least absolute remainders).
-
- Unless you plan for your language to run on only one machine, make the
- quotient and mod functions _well-defined_, so that portability is ensured.
-
- ----
-
- You might find additional insight in the paper
-
- ftp://ftp.netcom.com/pub/hb/hbaker/Gaussian.html (also .ps.Z)
-
- --
- www/ftp directory:
- ftp://ftp.netcom.com/pub/hb/hbaker/home.html
-
- Copyright (c) 1996 by Henry G. Baker. All rights reserved.
- ** Warning: Due to its censorship, CompuServe and its subscribers **
- ** are expressly prohibited from storing or copying this document **
- ** in any form. **
-